#ifndef _SecondPhase_H_
#define _SecondPhase_H_

/******************************************************************************

Description:
  This class handles the second phase of the algorithm. In this phase, output 
  from the first phase is used (this output is item counts and fp-tree) to find
  and output frequent items list. CLOSET+ algorithm is used to create projected
  fp-trees and these trees are in turn used to mine for frequent closed 
  itemsets.

  This file also includes definition for the Prefix class. This is used during
  mining of fp-trees and it represents prefix for itemsets. See CLOSET+ article
  for more info.

Notes:
  For sorting (algorithm:sort()) we need RandomAccessIterator's which are 
  provided by Vector, and not List. That is why we use Vector structures on
  everything we need to sort, although deleting from a vector is O(n) compared
  to O(1) with lists.

Date: 31/10/2008
Author: Tayfun Sen
Website: http://blog.tayfunsen.com
 
 *****************************************************************************/


// Standard libraries.
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <ext/hash_map>
#include <vector>
#include <algorithm>
#include <time.h>
// Boost libraries for serializing hash_map's.
#include <boost/tokenizer.hpp>
#include <boost/archive/tmpdir.hpp>
#include <boost/archive/text_oarchive.hpp>
#include <boost/archive/text_iarchive.hpp>
#include <boost/serialization/base_object.hpp>
#include <boost/serialization/utility.hpp>
#include <boost/serialization/hash_map.hpp>
#include <boost/serialization/map.hpp>
#include <boost/serialization/string.hpp>
#include <boost/mpi/environment.hpp>
#include <boost/mpi/communicator.hpp>
#include <boost/mpi.hpp>
// Custom libraries and headers.
#include "shared.hpp"
#include "Globals.hpp"
#include "Functors.hpp"
#include "Tree.hpp"
#include "FirstPhase.hpp"
#include "ResultTree.hpp"
#include "Prefix.hpp"


using namespace std;
using namespace boost;
using namespace __gnu_cxx;

// Tell boost to never track ResultTree objects. Thus, we can serialize it 
// without making a const_cast.
// See: http://www.boost.org/doc/libs/1_32_0/libs/serialization/doc/traits.html
// FIXME: Is this really needed? We didn't fall into a compile time trap.
// BOOST_CLASS_TRACKING(ResultTree, track_never);

/** 
 *  @brief Define this macro to avoid expensive MPI_Pack/Unpack calls on 
 *  homogeneous machines.
*/
#define BOOST_MPI_HOMOGENEOUS

class SecondPhase {
    public:
        SecondPhase(FirstPhase & fp) 
            : fpTree(fp.getFpTree()), globalCounts(fpTree.getItemCountsR()) {

            vector<HeaderInfo *> & headerVector = fpTree.getHeaderVector();
            int numberOfItems = headerVector.size();
            partSize = numberOfItems / Globals::size;
            // Notice that startIt is a reverse iterator.
            startIt = headerVector.rbegin() + partSize * Globals::rank;

            // The last node computes the remainder as well.
            if (Globals::rank == Globals::size - 1)
                partSize = numberOfItems - partSize * (Globals::size - 1);
        }

        int run();
        int projectTree(Prefix , HeaderInfo *, Tree &, Tree *);

    private:
        // Reference variables in a class have to be initialized in the 
        // initialization list of the constructor.
        // item counts are inside the tree.
        Tree & fpTree;
        // partSize denotes something different from FirstPhase. Here it denotes
        // the number of items a node will mine. In first phase it meant number
        // of transactions the node will mine. 
        int partSize;
        // Notice that startIt is a reverse iterator.
        vector<HeaderInfo *>::reverse_iterator startIt;
        // Result tree keeps track of the found frequent itemsets.
        ResultTree resultTree, mergedResult;
        // Global item counts reference is needed when populating the result
        // tree.
        hash_map<string, int> & globalCounts;
#ifdef USE_MPI     
        // MPI Communicator.
        mpi::communicator world;
#endif

        /************************************
         * Functions definitions start now.
         * *********************************/
        void mine();
        void reduceAndBcastResults();
        void pruneTransactions(vector< vector<string> * > &, 
                hash_map<string, int> &);
        void printHeaderVector();
        void printTransactions(vector< vector<string> *>);
};

#endif
